MPRI 1.24 - Algorithmes Randomisés (Nicolas Schabanel, CNRS - Université Paris Diderot)<br />[ Cours n°1 Partie A/C ]<br /><br />Cours n°1: Mar. Oct 30, 2012 - 16:30-19:30<br /> 1) Introduction aux algorithmes randomisés<br /> 2) Un algorithme randomisé pour Min-Cut<br /><br />Séance d'exercices n°1: Solutions aléatoires et dérandomisation<br /> 1) Analyse d'une partition aléatoire pour Max-Cut<br /> 2) Dérandomisation par la méthode de l'espérance conditionnelle<br /> 3) Dérandomisation par la construction d'un espace probabilisé de bits uniformes 2-à-2 indépendants<br /> 4) Généralisation à des bits uniformes k-à-k indépendants
